package com.template;

/**
 * 二叉树节点
 * @author shenb
 * @date 2022-02-22 22:21
 */
public class TreeNode {
  public int val;
  public TreeNode left;
  public TreeNode right;

  public TreeNode() {}

  public TreeNode(int val) {
    this.val = val;
  }

  public TreeNode(int val, TreeNode left, TreeNode right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }

  /**
   * 设定在最后一行的每个数字之间的间隔为3个空格，而在之上的每一层的间隔 树的结构示例：
   *      1
   *     / \
   *    2   3
   *   / \  / \
   *  4   5 6   7
   *
   * @return  树结构字符串
   */
  @Override
  public String toString() {
    int depth = getDepth();
    int width = 2 << (depth - 1);
    int writeDepth = depth * 2 - 1;
    int writeWidth = (width - 1) * 4 + 1;

    String[][] write = new String[writeDepth][writeWidth];


    fill(this, 0, writeWidth / 2 + 1, write, depth);

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < write.length; i++) {
      for (int i1 = 0; i1 < write[i].length; i1++) {
       if(write[i][i1] == null) {
          sb.append(" ");
       } else {
         sb.append(write[i][i1]);
       }
        if (i1 == width - 1) {
          sb.append("\n");
        }
      }
    }
    return sb.toString();
  }

  /**
   * 填充树的字符串结构
   * @param node  当前节点
   * @param row 所在行号
   * @param column  所在列号
   * @param write 待写入的字符串数组
   * @param treeDepth 树的最大深度
   */
  private void fill(TreeNode node, int row, int column, String[][] write, int treeDepth) {
    if (node == null) {
      return;
    }
    write[row][column] = String.valueOf(node.val);
    int curLevel = (row + 1) / 2;
    if (curLevel == treeDepth) {
      return;
    }
    int gap = treeDepth - curLevel -1;
    if (node.left != null) {
      write[row + 1][column - gap] = "/";
      fill(node.left, row + 2, column - gap * 2, write, treeDepth);
    }
    if (node.right != null) {
      write[row + 1][column + gap] = "\\";
      fill(node.right, row + 2, column + gap * 2, write, treeDepth);
    }
  }

  /**
   * 返回当前树的最大深度
   * @return  树的最大深度
   */
  public int getDepth() {
    return getTreeDepth(this);
  }

  /**
   * 计算一个树的最大深度
   * @param root  根节点
   * @return  最大深度
   */
  public static int getTreeDepth(TreeNode root) {
    return root == null ? 0 : (1 + Math.max(getTreeDepth(root.left), getTreeDepth(root.right)));
  }

  public static void main(String[] args) {
    TreeNode tree = new TreeNode(1, new TreeNode(2, null, new TreeNode(5)), new TreeNode(3 , new TreeNode(6), null));
    System.out.println(Random.randomTree());
  }
}
